/*
 * Copyright (c) 1997, 2013, Oracle and/or its affiliates. All rights reserved.
 * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 */

package java.util;
import java.util.Map.Entry;

/**
 * <p>这个类提供了Map接口的骨架实现，最小化了实现这个接口的努力。
 * 
 * <p>为了实现一个不可更改的map，编程者只需要继承这个类，
 * 并且提供entrySet方法的实现，entrySet方法返回map的映射的set视图。
 * 通常，返回的set会在AbstractSet上实现。
 * 这个set不应该支持add或者remove方法，它的迭代器不应该支持remove方法。
 * 
 * <p>为了实现一个可更改的map，编程者需要额外覆盖这个类的put方法（这个方法会抛出UnsupportedOperationException）
 * entrySet().iterator()返回的迭代器必须额外实现remove方法。
 * 
 * <p>编程者应该通常提供一个无参构造器和参数为map的构造器，根据Map接口规范的建议。
 * 
 * <p>这个类的每个非抽象方法的文档详细地描述了它的实现。
 * 如果实现的map要实现更有效的方法，这些方法可以被覆盖。
 *
 * @param <K> the type of keys maintained by this map
 * @param <V> the type of mapped values
 *
 * @author  Josh Bloch
 * @author  Neal Gafter
 * @see Map
 * @see Collection
 * @since 1.2
 */

public abstract class AbstractMap<K,V> implements Map<K,V> {
    /**
     * Sole constructor.  (For invocation by subclass constructors, typically
     * implicit.)
     */
    protected AbstractMap() {
    }

    // Query Operations

    /**
     * {@inheritDoc}
     *
     * <p>实现返回 <tt>entrySet().size()</tt>.
     */
    public int size() {
        return entrySet().size();
    }

    /**
     * {@inheritDoc}
     *
     * <p>实现返回 <tt>size() == 0</tt>.
     */
    public boolean isEmpty() {
        return size() == 0;
    }

    /**
     * {@inheritDoc}
     *
     * <p>这个实现迭代entrySet()，查找有着指定value的entry。
     * 如果一旦有entry被找到，返回true。
     * 如果迭代以没有找到entry停止，返回false。
     * 注意：这个实现需要与map的大小的线性相关的时间。
     *
     * @throws ClassCastException   {@inheritDoc}
     * @throws NullPointerException {@inheritDoc}
     */
    public boolean containsValue(Object value) {
        Iterator<Entry<K,V>> i = entrySet().iterator(); // 对entrySet迭代
        if (value==null) {
            while (i.hasNext()) {
                Entry<K,V> e = i.next();
                if (e.getValue()==null)
                    return true;
            }
        } else {
            while (i.hasNext()) {
                Entry<K,V> e = i.next();
                if (value.equals(e.getValue()))
                    return true;
            }
        }
        return false;
    }

    /**
     * {@inheritDoc}
     *
     * <p>这个实现迭代entrySet()，查找有着指定key的entry。
     * 如果一旦有entry被找到，返回true。
     * 如果迭代以没有找到entry停止，返回false。
     * 注意：这个实现需要与map的大小的线性相关的时间。
     * <p>许多实现会覆盖这个方法。
     *
     * @throws ClassCastException   {@inheritDoc}
     * @throws NullPointerException {@inheritDoc}
     */
    public boolean containsKey(Object key) {
        Iterator<Map.Entry<K,V>> i = entrySet().iterator();
        if (key==null) {
            while (i.hasNext()) {
                Entry<K,V> e = i.next();
                if (e.getKey()==null)
                    return true;
            }
        } else {
            while (i.hasNext()) {
                Entry<K,V> e = i.next();
                if (key.equals(e.getKey()))
                    return true;
            }
        }
        return false;
    }

    /**
     * {@inheritDoc}
     *
     * <p>这个实现迭代entrySet()，查找有着指定key的entry。
     * 如果一旦有entry被找到，返回entry的value。
     * 如果迭代以没有找到entry停止，返回null。
     * 注意：这个实现需要与map的大小的线性相关的时间。
     * <p>许多实现会覆盖这个方法。
     *
     * @throws ClassCastException            {@inheritDoc}
     * @throws NullPointerException          {@inheritDoc}
     */
    public V get(Object key) {
        Iterator<Entry<K,V>> i = entrySet().iterator();
        if (key==null) {
            while (i.hasNext()) {
                Entry<K,V> e = i.next();
                if (e.getKey()==null)
                    return e.getValue();
            }
        } else {
            while (i.hasNext()) {
                Entry<K,V> e = i.next();
                if (key.equals(e.getKey()))
                    return e.getValue();
            }
        }
        return null;
    }


    // Modification Operations

    /**
     * {@inheritDoc}
     *
     * @implSpec
     * This implementation always throws an
     * <tt>UnsupportedOperationException</tt>.
     *
     * @throws UnsupportedOperationException {@inheritDoc}
     * @throws ClassCastException            {@inheritDoc}
     * @throws NullPointerException          {@inheritDoc}
     * @throws IllegalArgumentException      {@inheritDoc}
     */
    public V put(K key, V value) {
        throw new UnsupportedOperationException();
    }

    /**
     * {@inheritDoc}
     *
     * <p>这个实现迭代entrySet()，查找有着指定key的entry。
     * 如果一旦有entry被找到，它的value通过entry的getValue方法得到，
     * entry通过Iterator的remove方法被删除，并将存储的value返回。
     * 如果迭代以没有找到entry停止，返回null。
     * 注意：这个实现需要与map的大小的线性相关的时间。
     * <p>许多实现会覆盖这个方法。
     * 
     * <p>注意：这个实现会抛出UnsupportedOperationException，
     * 如果entrySet的Iterator没有支持remove方法，并且map包含指定key对应的映射。
     *
     * @throws UnsupportedOperationException {@inheritDoc}
     * @throws ClassCastException            {@inheritDoc}
     * @throws NullPointerException          {@inheritDoc}
     */
    public V remove(Object key) {
        Iterator<Entry<K,V>> i = entrySet().iterator();
        Entry<K,V> correctEntry = null;
        if (key==null) {
            while (correctEntry==null && i.hasNext()) {
                Entry<K,V> e = i.next();
                if (e.getKey()==null)
                    correctEntry = e;
            }
        } else {
            while (correctEntry==null && i.hasNext()) {
                Entry<K,V> e = i.next();
                if (key.equals(e.getKey())) // 找到对应entry
                    correctEntry = e;
            }
        }

        V oldValue = null;
        if (correctEntry !=null) {
            oldValue = correctEntry.getValue();
            i.remove(); // 通过Iterator的remove方法删除
        }
        return oldValue;
    }


    // Bulk Operations

    /**
     * {@inheritDoc}
     * 
     * <p>这个实现迭代entrySet()，对迭代过程中返回的每个entry调用map的put操作
     * 
     * <p>注意：这个实现会抛出UnsupportedOperationException，
     * 如果这个map不支持put操作，并且指定map非空。
     *
     * @throws UnsupportedOperationException {@inheritDoc}
     * @throws ClassCastException            {@inheritDoc}
     * @throws NullPointerException          {@inheritDoc}
     * @throws IllegalArgumentException      {@inheritDoc}
     */
    public void putAll(Map<? extends K, ? extends V> m) {
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) // 对m.entrySet()迭代
            put(e.getKey(), e.getValue()); // 在这个map逐个放入
    }

    /**
     * {@inheritDoc}
     *
     * <p>这个实现调用 <tt>entrySet().clear()</tt>.
     *
     * <p>注意：这个实现会抛出UnsupportedOperationException，
     * 如果这个entrySet不支持clear操作
     *
     * @throws UnsupportedOperationException {@inheritDoc}
     */
    public void clear() {
        entrySet().clear();
    }


    // Views

    /**
     * 在第一次请求改视图的时候，下面的每个字段会被初始化，来拥有一个适当的视图的实例。
     *
     * <p>因为访问这些字段没有执行同步，所以希望java.util.Map的使用这些字段的视图类，
     * 没有非final的字段（或者除了outer，this之外的任何字段都是final的）。
     * 遵守这个规则会让在这些字段上的竞争变得良性。
     *
     * <p>还有一点也是有必要的：实现只能读取这个字段仅仅一次，如：
     * <pre> {@code
     * public Set<K> keySet() {
     *   Set<K> ks = keySet;  // single racy read
     *   if (ks == null) {
     *     ks = new KeySet();
     *     keySet = ks;
     *   }
     *   return ks;
     * }
     *}</pre>
     */
    transient Set<K>        keySet;
    transient Collection<V> values;

    /**
     * {@inheritDoc}
     *
     * <p>实现返回一个AbstractSet的子类。
     * 子类的Iterator方法返回了基于这个map的entrySet的迭代器的一个包装对象。
     * size方法对应map的size方法，contains方法对应map的containsKey方法。
     *
     * <p>这个set在这个方法被第一次调用时，被创建，并且对接下来所有的调用，返回这个set。
     * 不会执行同步，所以有很小的可能性，多次调用这个方法不会返回同一个set。
     */
    public Set<K> keySet() {
        Set<K> ks = keySet;
        if (ks == null) { // keySet没有被创建，才创建，单例模式
            ks = new AbstractSet<K>() {
                public Iterator<K> iterator() {
                    return new Iterator<K>() {
                        private Iterator<Entry<K,V>> i = entrySet().iterator();  // 根据entrySet的Iterator

                        public boolean hasNext() {
                            return i.hasNext();
                        }

                        public K next() {
                            return i.next().getKey(); // entrySet的getkey
                        }

                        public void remove() {
                            i.remove(); // 删除entrySet
                        }
                    };
                }

                public int size() {
                    return AbstractMap.this.size(); // map自己的size
                }

                public boolean isEmpty() {
                    return AbstractMap.this.isEmpty(); // map自己的isEmpty
                }

                public void clear() {
                    AbstractMap.this.clear(); // map自己的clear
                }

                public boolean contains(Object k) {
                    return AbstractMap.this.containsKey(k); // map自己的containsKey
                }
            };
            keySet = ks; // 创建后，赋值给keySet
        }
        return ks;
    }

    /**
     * {@inheritDoc}
     *
     * <p>实现返回一个AbstractCollection的子类。
     * 子类的Iterator方法返回了基于这个map的entrySet的迭代器的一个包装对象。
     * size方法对应map的size方法，contains方法对应map的containsValue方法。
     *
     * <p>这个collection在这个方法被第一次调用时，被创建，并且对接下来所有的调用，返回这个collection。
     * 不会执行同步，所以有很小的可能性，多次调用这个方法不会返回同一个collection。
     */
    public Collection<V> values() {
        Collection<V> vals = values;
        if (vals == null) {
            vals = new AbstractCollection<V>() {
                public Iterator<V> iterator() {
                    return new Iterator<V>() {
                        private Iterator<Entry<K,V>> i = entrySet().iterator();

                        public boolean hasNext() {
                            return i.hasNext();
                        }

                        public V next() {
                            return i.next().getValue();
                        }

                        public void remove() {
                            i.remove();
                        }
                    };
                }

                public int size() {
                    return AbstractMap.this.size();
                }

                public boolean isEmpty() {
                    return AbstractMap.this.isEmpty();
                }

                public void clear() {
                    AbstractMap.this.clear();
                }

                public boolean contains(Object v) {
                    return AbstractMap.this.containsValue(v);
                }
            };
            values = vals;
        }
        return vals;
    }

    public abstract Set<Entry<K,V>> entrySet();


    // Comparison and hashing

    /**
     * <p>将指定对象与这个map进行相等性的比较。
     * 如果指定对象也是一个map，两个map代表相同的映射，返回true。
     * 更正式地，两个map m1和m2代表相同的映射，如果m1.entrySet().equals(m2.entrySet())。
     * 这保证equals方法在不同的Map接口的实现间工作正常。
     *
     * <p>这个实现一开始检查指定对象是否是这个map自己，如果是，返回true。
     * 然后，检查指定对象是否是一个大小与这个map的大小相同的map，如果不是，返回false。
     * 如果是，迭代这个map的entrySet集合，检查指定map是否包含这个map包含的每个映射。
     * 如果指定map不包含这样的一个映射，返回false。
     * 如果迭代结束，返回true。
     *
     * @param o object to be compared for equality with this map
     * @return <tt>true</tt> if the specified object is equal to this map
     */
    public boolean equals(Object o) {
        if (o == this) // 自己
            return true;

        if (!(o instanceof Map)) // 类型
            return false;
        Map<?,?> m = (Map<?,?>) o;
        if (m.size() != size()) // 大小
            return false;

        try {
            Iterator<Entry<K,V>> i = entrySet().iterator(); // 对自己迭代
            while (i.hasNext()) {
                Entry<K,V> e = i.next();
                K key = e.getKey();
                V value = e.getValue();
                if (value == null) {
                    if (!(m.get(key)==null && m.containsKey(key)))
                        return false;
                } else {
                    if (!value.equals(m.get(key))) // 自己的value与 m.get(key)是否相同
                        return false;
                }
            }
        } catch (ClassCastException unused) {
            return false;
        } catch (NullPointerException unused) {
            return false;
        }

        return true;
    }

    /**
     * 返回map的hashcode。
     * map的hashcode根据map的entrySet()视图的每个entry的hashcode的和定义。
     * 这保证对于任意两个map m1和m2，m1.equals(m2)代表m1.hashCode()==m2.hashCode()，
     * 根据Object.hashCode的通常约定。
     *
     * <p>这个实现迭代了entrySet，对每个entry，调用hashcode方法，将结果加起来
     *
     * @return the hash code value for this map
     * @see Map.Entry#hashCode()
     * @see Object#equals(Object)
     * @see Set#equals(Object)
     */
    public int hashCode() {
        int h = 0;
        Iterator<Entry<K,V>> i = entrySet().iterator(); // 对entrySet迭代
        while (i.hasNext())
            h += i.next().hashCode(); // 调用entry自己的hashcode，加起来
        return h;
    }

    /**
     * 返回这个map的字符串表示。
     * 字符串表示由一个key-value映射的列表构成，顺序为entrySet迭代器返回的顺序，以大括号{}包围。
     * 相邻的映射以字符逗号和空格, 分隔。
     * 每个key-value映射以key然后是等号=  然后是关联的value。
     * key和value被转换成字符串，通过String.valueOf()方法
     *
     * @return a string representation of this map
     */
    public String toString() {
        Iterator<Entry<K,V>> i = entrySet().iterator();
        if (! i.hasNext())
            return "{}";

        StringBuilder sb = new StringBuilder();
        sb.append('{'); // 以大括号进行包围
        for (;;) {
            Entry<K,V> e = i.next();
            K key = e.getKey();
            V value = e.getValue(); // 对entrySet进行迭代
            sb.append(key   == this ? "(this Map)" : key);
            sb.append('='); // 中间是等号
            sb.append(value == this ? "(this Map)" : value);
            if (! i.hasNext())
                return sb.append('}').toString(); // 没有了加大括号，否则加逗号和空格
            sb.append(',').append(' ');
        }
    }

    /**
     * 返回这个AbstractMap实例的浅复制：key和values它们自己没有被复制。
     *
     * @return a shallow copy of this map
     */
    protected Object clone() throws CloneNotSupportedException {
        AbstractMap<?,?> result = (AbstractMap<?,?>)super.clone();
        result.keySet = null;
        result.values = null;
        return result;
    }

    /**
     * 为了SimpleEntry和SimpleImmutableEntry的工具方法。
     * 对于相等性的测试，检查null值。
     *
     * NB: Do not replace with Object.equals until JDK-8015417 is resolved.
     */
    private static boolean eq(Object o1, Object o2) {
        return o1 == null ? o2 == null : o1.equals(o2);
    }

    /**
     * 实现注意：SimpleEntry和SimpleImmutableEntry在不相关的类间是不同的，
     * 即使它们共享一些代码。
     * 因为你不能在一个子类中，增加或者减去字段的final修饰符，
     * 所以它们不能共享形式，并且重复的代码太少了，不足以公开共同的抽象类
     *
     */    

    /**
     * 一个entry保存一个key和value。
     * value可以用setValue方法改变。
     * 这个类简化了自定义的map实现的过程。
     * 例如，这可以在Map.entrySet().toArray方法返回SimpleEntry实例的数组，比较方便。
     *
     * @param <K>
     * @param <V>
     */
    public static class SimpleEntry<K,V>
        implements Entry<K,V>, java.io.Serializable
    {
        private static final long serialVersionUID = -8499721149061103585L;

        private final K key; // key为final
        private V value; // value可变

        /**
         * 使用指定的key和value创建一个entry，代表一个映射
         *
         * @param key the key represented by this entry
         * @param value the value represented by this entry
         */
        public SimpleEntry(K key, V value) {
            this.key   = key;
            this.value = value;
        }

        /**
         * 创建一个entry，代表与指定entry相同的映射。
         *
         * @param entry the entry to copy
         */
        public SimpleEntry(Entry<? extends K, ? extends V> entry) {
            this.key   = entry.getKey();
            this.value = entry.getValue();
        }

        /**
         * 返回这个entry对应的key
         *
         * @return the key corresponding to this entry
         */
        public K getKey() {
            return key;
        }

        /**
         * 返回这个entry对应的value。
         *
         * @return the value corresponding to this entry
         */
        public V getValue() {
            return value;
        }

        /**
         * 将entry的value替代为指定的value
         *
         * @param value new value to be stored in this entry
         * @return the old value corresponding to the entry
         */
        public V setValue(V value) {
            V oldValue = this.value;
            this.value = value;
            return oldValue;
        }

        /**
         * 将指定对象与这个entry进行相等性的比较。
         * 如果给定的对象也是一个map的entry，两个entry代表同样的映射，返回true。
         * 更正式地，两个entry e1和e2代表同样的映射，如果：
         * <pre>
         *   (e1.getKey()==null ?
         *    e2.getKey()==null :
         *    e1.getKey().equals(e2.getKey()))
         *   &amp;&amp;
         *   (e1.getValue()==null ?
         *    e2.getValue()==null :
         *    e1.getValue().equals(e2.getValue()))</pre>
         * 这保证equals方法在不同的Map.Entry接口的实现间，工作正常。
         *
         * @param o object to be compared for equality with this map entry
         * @return {@code true} if the specified object is equal to this map
         *         entry
         * @see    #hashCode
         */
        public boolean equals(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            return eq(key, e.getKey()) && eq(value, e.getValue()); // 两者的key和value都相同
        }

        /**
         * 返回这个map entry的hashcode。hashcode安装如下定义（key和value的hashcode进行亦或）：
         * <pre>
         *     (e.getKey()==null   ? 0 : e.getKey().hashCode()) ^
         *     (e.getValue()==null ? 0 : e.getValue().hashCode())
         * </pre>
         * 这保证e1.equals(e2)代表e1.hashCode()==e2.hashCode()，
         * 对于任何两个entry e1和e2，按照Object的hashCode的要求
         *
         * @return the hash code value for this map entry
         * @see    #equals
         */
        public int hashCode() {
            return (key   == null ? 0 :   key.hashCode()) ^
                   (value == null ? 0 : value.hashCode());
        }

        /**
         * 返回这个entry的字符串表示。
         * 字符串表示先是key的字符串表示，然后是等号=，然后是value的字符串表示
         *
         * @return a String representation of this map entry
         */
        public String toString() {
            return key + "=" + value;
        }

    }

    /**
     * 一个entry保存不可更改的一个key和value。
     * 这个类不支持setValue操作
     * 这个类对返回线程安全的key-value映射的快照的方法，十分方便。
     *
     * @since 1.6
     */
    public static class SimpleImmutableEntry<K,V>
        implements Entry<K,V>, java.io.Serializable
    {
        private static final long serialVersionUID = 7138329143949025153L;

        private final K key;
        private final V value; // 都是final的

        /**
         * Creates an entry representing a mapping from the specified
         * key to the specified value.
         *
         * @param key the key represented by this entry
         * @param value the value represented by this entry
         */
        public SimpleImmutableEntry(K key, V value) {
            this.key   = key;
            this.value = value;
        }

        /**
         * Creates an entry representing the same mapping as the
         * specified entry.
         *
         * @param entry the entry to copy
         */
        public SimpleImmutableEntry(Entry<? extends K, ? extends V> entry) {
            this.key   = entry.getKey();
            this.value = entry.getValue();
        }

        /**
         * Returns the key corresponding to this entry.
         *
         * @return the key corresponding to this entry
         */
        public K getKey() {
            return key;
        }

        /**
         * Returns the value corresponding to this entry.
         *
         * @return the value corresponding to this entry
         */
        public V getValue() {
            return value;
        }

        /**
         * Replaces the value corresponding to this entry with the specified
         * value (optional operation).  This implementation simply throws
         * <tt>UnsupportedOperationException</tt>, as this class implements
         * an <i>immutable</i> map entry.
         *
         * @param value new value to be stored in this entry
         * @return (Does not return)
         * @throws UnsupportedOperationException always
         */
        public V setValue(V value) {
            throw new UnsupportedOperationException(); // 不支持setValue
        }

        /**
         * Compares the specified object with this entry for equality.
         * Returns {@code true} if the given object is also a map entry and
         * the two entries represent the same mapping.  More formally, two
         * entries {@code e1} and {@code e2} represent the same mapping
         * if<pre>
         *   (e1.getKey()==null ?
         *    e2.getKey()==null :
         *    e1.getKey().equals(e2.getKey()))
         *   &amp;&amp;
         *   (e1.getValue()==null ?
         *    e2.getValue()==null :
         *    e1.getValue().equals(e2.getValue()))</pre>
         * This ensures that the {@code equals} method works properly across
         * different implementations of the {@code Map.Entry} interface.
         *
         * @param o object to be compared for equality with this map entry
         * @return {@code true} if the specified object is equal to this map
         *         entry
         * @see    #hashCode
         */
        public boolean equals(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            return eq(key, e.getKey()) && eq(value, e.getValue());
        }

        /**
         * Returns the hash code value for this map entry.  The hash code
         * of a map entry {@code e} is defined to be: <pre>
         *   (e.getKey()==null   ? 0 : e.getKey().hashCode()) ^
         *   (e.getValue()==null ? 0 : e.getValue().hashCode())</pre>
         * This ensures that {@code e1.equals(e2)} implies that
         * {@code e1.hashCode()==e2.hashCode()} for any two Entries
         * {@code e1} and {@code e2}, as required by the general
         * contract of {@link Object#hashCode}.
         *
         * @return the hash code value for this map entry
         * @see    #equals
         */
        public int hashCode() {
            return (key   == null ? 0 :   key.hashCode()) ^
                   (value == null ? 0 : value.hashCode());
        }

        /**
         * Returns a String representation of this map entry.  This
         * implementation returns the string representation of this
         * entry's key followed by the equals character ("<tt>=</tt>")
         * followed by the string representation of this entry's value.
         *
         * @return a String representation of this map entry
         */
        public String toString() {
            return key + "=" + value;
        }

    }

}
